package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:13
 * @Description:归并排序
 * 思想：递归+分治
 * 步骤：
 *      1.划分小数组
 *      2.合并子数组
 * 最好、最坏、平均时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 * 是否是初始化数据的影响：false
 * 稳定排序
 *
 */
public class MergeSort {
    public static void mergeSort(int[] arr,int n){
        if(arr == null||n<2) return;
        merge_sort(arr,0,n-1);
    }

    //分解过程，大数组分成小数组处理
    private static void merge_sort(int[] arr, int l, int r) {
        if(l==r) return;
        //将数据不断划分小数组，不断递归
        int mid = l+((r-l)>>2);
        merge_sort(arr,l,mid);
        merge_sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    //合并数组
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r-l+1];//辅助数组
        int i= l,j = mid+1,k=0;
        //当两个数组没有遍历完成时，每次遍历将较小的元素放入数组中
        while(i<=mid && j<=r){
            temp[k++] = arr[i]<arr[j]?arr[i++]:arr[j++];
        }
        //
        while(i<=mid){temp[k++] = arr[i++];}
        while(j<=r){temp[k++] = arr[j++];}
        //将数据拷贝会原数组
        for(i = 0;i<temp.length;i++){
            arr[l+i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,6,4,12,8,18,16};
        mergeSort(arr,arr.length);
        for (int i : arr) {
            System.out.print(" "+i);
        }
    }
}
